Network processors (also called communications processors) of the prior art may perform one or more of the following functions (called “network processing functions”): parsing, searching, resolving and modifying. During parsing, a network processor analyzes and classifies the contents of the header and fields. During searching, tables are searched for a match between the content that was classified and pre-defined content and rules. During resolving, the destination and quality of service (QoS) requirements are resolved and the packet/cell is routed to its destination. During modifying, where necessary, the packet/cell is modified, e.g. certain fields (such as time to live and checksum) within the packet/cell are changed. Examples of commercially available network processors include: Intel's IXP1200, Agere's Payload Plus, AMCC's nP7250, IBM's PowerNP NP4GS3, Motorola's C-Port C-5 and Vitesse's IQ2000.
A network processor of the type described above is typically coupled to and used with a traffic manager and/or a switch fabric. Either or both devices (traffic manager and/or switch fabric) may perform one or more of the following functions: queuing and output scheduling (round robin, weighted fair queuing), policing of traffic flows to assure quality of service, traffic shaping (e.g. to meet delay or jitter requirements), statistics collection, congestion management and provisioning. Examples of commercially available devices that perform switch fabric functions include: Motorola's Q5 TMC, and AMCC's nPX5710/nPX5720 (together referred to as nPX5700).
For traffic management as well as for switching, each packet/cell must be stored in memory and later transmitted. The above-described functions may be implemented together in a chipset consisting of two chips: a traffic manager (such as AMCC's nPX5710) and a memory manager (such as AMCC's nPX5720). The just-described two chips are normally used together and each may have four ports, each port being coupled to a network processor by serial links operating at 2.5 Gbps or 10 Gbps.
Buffering of traffic is typically implemented via an external memory attached to the memory manager (which is also called a “switch fabric”). Typical requirements in today's networks may require traffic up to two hundred and fifty six thousand (256K) queues to be managed. In some implementations, at any given time, only information related to a subset of these queues (e.g. up to eight thousand queues) may be cached on chip (e.g. in DDR SDRAM or RDRAM) by taking advantage of statistical multiplexing (i.e. the likelihood that the incoming traffic belongs to more than eight thousand queues is very low). Therefore, eight thousand queues (containing packets/cells) are stored in a buffering chip (such as AMCC's nPX5720) having embedded DRAM channels for example, and these queues are managed by a control logic chip (such as AMCC's nPX5710). These two chips when used together act as a switch fabric and traffic manager.
A prior art network processor 110 may be used with a prior art traffic manager 120 as illustrated in FIG. 1. Traffic manager 120 is coupled to an external memory 130 that temporarily holds packet fragments in queues. Note that each packet fragment (of variable length) may itself be divided up into one or more cells (of fixed length). Traffic manager 120 typically contains a queue manager 121 which (in certain prior art known to the inventors) is hardwired to automatically write and link each packet fragment or cell sent by network processor 110 to a queue identified by network processor 110 on a bus 116 (FIG. 1). Network processor 110 includes a processing unit 111 that identifies a queue number for each packet fragment or cell, based on a header of the packet fragment. Incoming packet fragments are temporarily stored in an ingress FIFO memory 112 inside network processor 110 while awaiting processing by processing unit 111.
Such a queue manager 121 of the prior art traffic manager 120 does not (to the inventors' knowledge) perform any actions on a packet fragment (or cell) when being stored in memory 130, other than to write and link the fragment (or cell) directly into a queue in a single unitary operation (that is uninterruptible). Specifically, the inventors know of no instruction or command that can be issued to a prior art queue manager 121 to reassemble out-of-order fragments (or cells). Instead, a queue manager 121 of the prior art simply accepts packet fragments (or cells) without any explicit instruction, and automatically adds them to the identified queue.
The packet fragments which are stored in queues in external memory 130 are processed for transfer therefrom by a scheduler 122 that is included in prior art traffic manager 120. Scheduler 122 of the prior art may schedule transfer of packet fragments from each queue based on a number of criteria, for example, priority and/or rate (shaping and limiting), minimum bandwidth guarantee and maximum bandwidth limit, and any other quality of service (QOS) parameters known in the prior art. Scheduler 122 may implement, for example, a weighted round robin (WRR) mechanism, to schedule the queues for data transfer therefrom.
At an appropriate time (as determined by scheduler 122), the packet fragments in a queue are transferred to network processor 110 (or to another network processor). Processing unit 111 forwards the packet fragments towards their destination. Note that re-ordering of packet fragments and reassembly of a packet is performed in another device (not shown) which is located down stream of network processor 110.
Incorporated by reference herein in their entirety are the following references:
“A Fully-Programmable Memory Management System Optimizing Queue Handling at Multi Gigabit Rates” by G. Kornaros, I. Papaefasthathiou, A. Nikologiannis and N. Zervos, pages 54-59 published at DAC 2003, Jun. 2-6, 2003, Anaheim, Calif.;
U.S. Pat. No. 6,307,860 granted to Joffe, et al. on Oct. 23, 2001, and entitled “Systems and methods for data transformation and transfer in networks”;
U.S. Pat. No. 6,330,584 granted to Joffe, et al. on Dec. 11, 2001, and entitled “Systems and methods for multi-tasking, resource sharing and execution of computer instructions”;
U.S. Pat. No. 5,901,147 granted to Joffe on May 4, 1999, and entitled “Apparatus and methods to change thresholds to control congestion in ATM switches”; and
U.S. Pat. No. 6,128,278 granted to Joffe, et al. on Oct. 3, 2000 and entitled “Cell queuing in ATM switches.”